The present invention is generally directed to apparatus and method for encoding and decoding of binary data using error correction coding (ECC) systems which permit modular implementation. More particularly, the present invention is directed to error correction codes constructed from permuted versions of a base form of a parity check matrix.
The utilization of error correction and detection codes in electronic and data processing and information transmission systems is becoming more and more important for several reasons. In particular, increased criticality in applications and data security concerns require ever increasing levels of reliability in transmission. Furthermore, the use of high density, very large scaled integrated circuit chips for use in memory systems has increased the potential for the occurrence of soft errors such as those induced by alpha particle background radiation. Additionally, the use of integrated circuit chips has led to smaller and smaller circuits communicating and interacting at much higher information transmission rates. Accordingly, it has become more desirable to be able to protect memory and system integrity against the occurrence of transmission and storage errors. Nonetheless, as desirable as it is to incorporate error correction circuitry in various applications, it is also very desirable to insure that the correction scheme is efficient and robust while at the same time consuming a relatively small area on circuit chip devices. One of the ways of achieving this objective is to devise compact circuits which can be packaged together easily and for which the number of distinct subcircuits or parts is as small as possible. Furthermore, particularly in error correction associated with computer memory systems and other computer circuits, it is important that as little overhead time or delay cost be incurred as the result of the inclusion of error correction circuitry. Thus it is important to construct error correction circuitry both for decoding and encoding in which there are as few logic levels as possible.
In addition to all of the desirable code features that are described above that should be present in error correction coding systems, it is also desirable that the code be based upon certain well known algebraic concepts that are prevalent in the construction of error correction codes. In particular, codes which can be described as being based upon irreducible polynomials whose roots lie in a Galois field have been found to possess a number of positive qualities. A well known class of such codes are referred to as to the Bose-Chadhuri-Hocquenghem (BCH) codes. These codes are based upon parity check matrices which are formed from powers of irreducible polynomials over the binary field. Those polynomials represent field elements. The Galois field provides an extension field in which the roots can be defined, described and manipulated. The desirability of basing codes on such algebraic and systematic coding theories is that the principles developed in behalf of one code for a given application are thus readily extendable to other codes in other applications with different numbers of check, parity or information digits.
The effectiveness of a code is generally described in terms of the minimum distance that exists between code words, as measured in accordance with the Hamming distance metric. In particular, in one embodiment, the present invention is directed by way of example, toward the construction of codes which correct double errors and which detect triple errors. Such codes require a minimum code distance d of six. Such codes are referred to as double error correcting-triple error detecting (DEC-TED) codes or "d=6" codes.